const int MAXN = 45;
struct GraphMatch {
	int Next[MAXN], spouse[MAXN], parent[MAXN];
	int findb(int a) {return parent[a] == a ? a : parent[a] = findb(parent[a]);}
	void together(int a, int b) {
		a = findb(a); b = findb(b);
		if (a != b) parent[a] = b;
	}
	vector<int> E[MAXN];
	int N, Q[MAXN], bot;
	int mark[MAXN], visited[MAXN];
	int findLCA(int x,int y) {
		static int Ts = 0; Ts++;
		while (1) {
			if (x!=-1) {
				x = findb(x);
				if (visited[x] == Ts) return x;
				visited[x] = Ts;
				if (spouse[x] != -1) x = Next[spouse[x]];
				else x = -1;
			}
			swap(x,y);
		}
	}
	void goup(int a,int p){
		while (a != p){
			int b = spouse[a], c = Next[b];
			if (findb(c) != p) Next[c] = b;
			if (mark[b] == 2) mark[Q[bot++] = b] = 1;
			if (mark[c] == 2) mark[Q[bot++] = c] = 1;
			together(a, b);
			together(b, c);
			a = c;
		}
	}
	void findaugment(int s){
		for (int i = 0; i < N; i++) {
			Next[i] = -1; parent[i] = i;
			mark[i] = 0; visited[i] = -1;
		}
		Q[0] = s; bot = 1; mark[s] = 1;
		for (int head = 0; spouse[s] == -1 && head < bot; head++){
			int x = Q[head];
			for (int i = 0; i < E[x].size(); i++){
				int y = E[x][i];
				if (spouse[x] != y && findb(x) != findb(y) && mark[y] != 2){
					if (mark[y] == 1){
						int p = findLCA(x, y);
						if (findb(x) != p) Next[x] = y;
						if (findb(y) != p) Next[y] = x;
						goup(x, p); goup(y, p);
					} else if (spouse[y] == -1){
						Next[y] = x;
						for (int j = y; j != -1;){
							int k = Next[j], l = spouse[k];
							spouse[j] = k; spouse[k] = j;
							j = l;
						}
						break;
					}else{
						Next[y] = x;
						mark[Q[bot++] = spouse[y]] = 1;
						mark[y] = 2;
					}
				}
			}
		}
	}
	void init(int n) {
		N = n;
		for (int i = 0; i < N; ++i) E[i].clear();
	}
	void addEdge(int a, int b) {
		E[a].push_back(b);
		E[b].push_back(a);
	}
	int maxMatch() {
		int ret = 0;
		for (int i = 0; i < N; ++i) spouse[i] = -1;
		for (int i = 0; i < N; ++i)
			if (spouse[i] == -1) findaugment(i);
		for (int i = 0; i < N; ++i) 
			if (spouse[i] != -1) ++ret;
		return ret;
	}
};
